package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         79,
		Discription: "矩阵内的单词搜索",
		Level:       2,
		Labels: map[string]int{
			"回溯": 1,
			"矩阵": 1,
		},
	})
}

func Exist(board [][]byte, word string) bool {
	m := len(board)
	n := len(board[0])
	usedMap := make([][]bool, m)
	for i := 0; i < m; i++ {
		usedMap[i] = make([]bool, n)
	}

	var dfs func(int, int, int) bool
	dfs = func(index int, i int, j int) bool {
		if board[i][j] != word[index] {
			return false
		}

		usedMap[i][j] = true
		index++
		if index == len(word) {
			return true
		}

		if j > 0 && !usedMap[i][j-1] {
			found := dfs(index, i, j-1)
			if found {
				return true
			}
		}

		if j < n-1 && !usedMap[i][j+1] {
			found := dfs(index, i, j+1)
			if found {
				return true
			}
		}

		if i > 0 && !usedMap[i-1][j] {
			found := dfs(index, i-1, j)
			if found {
				return true
			}
		}

		if i < m-1 && !usedMap[i+1][j] {
			found := dfs(index, i+1, j)
			if found {
				return true
			}
		}

		//四个方向都无解的话返回false，记得把usedMap重置
		usedMap[i][j] = false
		return false
	}

	//矩阵中的每一个点都回溯搜一次
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if dfs(0, i, j) {
				return true
			}
		}
	}

	return false
}
